package logique.calculateur;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.PriorityQueue;

import logique.preferences.PreferencesUtilisateur;
import logique.reseau.Troncon;
import logique.reseau.Ville;

/**
 * Implémente l'algorithme de Dijkstra classique sur un réseau
 * 
 *
 */
public class Dijkstra {
	
	private Calculateur calculateur;
	
	/**
	 * Liste des tronçons déjà traversé et pas encore développés. 
	 * Régulièrement mise à jour (add - remove) lors des parcours.
	 */
	private PriorityQueue<Ville> villesTri;


	private HashMap<Ville, Integer> poidsVilles;
	
	/**
	 * Indique pour chaque ville, le tronçon à emprunter pour y acceder.
	 */
	private HashMap<Ville, Troncon> predecesseurs;
	
	
	/**
	 * Dernière ville atteinte par Dijkstra.<br />
	 * 'fin' dans le cas d'une seule fin.<br />
	 * L'une des 'fins' dans le cas de plusieurs fins possibles
	 */
	private Ville lastVille;
	
	public Dijkstra(Calculateur c){
		calculateur = c;
	}
	
	/**
	 * Fait tourner l'algorithme de Dijkstra sur le réseau r, en cherchant le chemin
	 * le plus court de 'debut' à 'fin'
	 * 
	 * @param r Réseau sur lequel porte la recherche
	 * @param debut Noeud de départ, représenté par un entier
	 * @param fin Noeud d'arrivée, représenté par un entier
	 * @return 0
	 */
	public LinkedList<Troncon> calculPCC(Ville debut, Ville fin, PreferencesUtilisateur prefs){

		ArrayList<Ville> temp = new ArrayList<Ville>();
		temp.add(fin);
		
		return calculPCC(debut, temp, prefs);
	}
	
	/**
	 * Fait tourner l'algorithme de Dijkstra sur le réseau r, en cherchant le chemin
	 * le plus court de 'debut' au premier élément de 'fins' rencontré
	 * 
	 * @param r Réseau sur lequel porte la recherche
	 * @param debut Noeud de départ
	 * @param fins Noeuds d'arrivée
	 * @return 0
	 */
	public LinkedList<Troncon> calculPCC(Ville debut, ArrayList<Ville> fins, PreferencesUtilisateur prefs){

		
		/* -------------------------------------------------------------
		XXX						Déclarations
		-------------------------------------------------------------- */

		LinkedList<Troncon> solution = new LinkedList<Troncon>();

		/* -------------------------------------------------------------
		XXX						Initialisations
		-------------------------------------------------------------- */


		poidsVilles = new HashMap<Ville, Integer>();
		poidsVilles.put(debut, 0);
		
		// TODO calculer précisément la taille de la queue
		villesTri = new PriorityQueue<Ville>(10, new Comparator<Ville>() {

			public int compare(Ville v1, Ville v2) {
				if (getPoidsVille(v1) < getPoidsVille(v2))
					return -1;
				else if( v1.equals(v2) )
					return 0;
				return 1;
			}
			
		});
		villesTri.add(debut);
		
		predecesseurs = new HashMap<Ville, Troncon>();

		Ville best = debut;
		

		/* -------------------------------------------------------------
		XXX						Boucle principale
		-------------------------------------------------------------- */

		/* 
		 * Tant qu'on n'a pas visité tous les noeuds et qu'on n'a pas atteint 'fin', 
		 * on prend le meilleur noeud atteint et on visite tous ses voisins en mettant 
		 * à jour les poids s'ils sont inférieurs.
		 */
		while ( !villesTri.isEmpty() && !fins.contains(best)) synchronized(best){ 

			
			for (Troncon t : best.getTroncons()) synchronized(t){
				// initialisation des evaluations
				if( t.getEvaluations() == null ){
					t.setEvaluations(new Evaluations(prefs, t));
					calculateur.addEvaluation(t.getEvaluations());
				}
				
				int score = getPoidsVille(best) + t.getEvaluations().getScore();
				Ville direction = null;
				if( t.getVille1().equals(best) ){
					direction = t.getVille2();
				}else if( t.getVille2().equals(best) ){
					direction = t.getVille1();
				}

				if ( t.getEvaluations().getScore() > 0 && score < getPoidsVille(direction) )
				{
					// mise à jour des structures
					poidsVilles.put(direction, score);
					villesTri.add(direction);
					predecesseurs.put(direction, t);
				}

			}

			// Plus petit élément de noeudTri : 
			
			best = villesTri.poll();

		}

		/* -------------------------------------------------------------
		XXX					Fin de l'algorithme							
		-------------------------------------------------------------- */
		
		// Dernière ville atteinte
		lastVille = best;
		
		Troncon t = predecesseurs.get(best);
		Ville v = best;
		while ( t != null ){
			solution.addFirst(t);
			if( t.getVille1().equals(v) ){
				v = t.getVille2();
			}else if( t.getVille2().equals(v) ){
				v = t.getVille1();
			}
			t = predecesseurs.get(v);
		}

		villesTri.clear();
		predecesseurs.clear();
		poidsVilles.clear();
		
		villesTri = null;
		predecesseurs = null;
		poidsVilles = null;

		return solution;
	}
	
	private int getPoidsVille(Ville v){
		if( poidsVilles.containsKey(v) ){
			return poidsVilles.get(v);
		}
		return Integer.MAX_VALUE;
	}
	
	public Ville getLastVille() {
		return lastVille;
	}
	
}
